package codetop.microsoft.T200;

/**
 * @Author: 18362
 * @Create: 2022-08-13 23:36:41 星期六
 */
class Solution {

    private static final int[] dx = new int[] {0, 0, -1, 1};
    private static final int[] dy = new int[] {-1, 1, 0, 0};
    private char[][] grid;
    private int m;
    private int n;
    private boolean[][] visited;

    public int numIslands(char[][] grid) {
        int num = 0;
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(i, j);
                    num++;
                }
            }
        }
        return num;
    }

    private void dfs(int x, int y) {
        visited[x][y] = true;
        for (int i=0; i<4; ++i) {
            int newx = x + dx[i], newy = y + dy[i];
            if (isValid(newx, newy)) {
                dfs(newx, newy);
            }
        }
    }

    private boolean isValid(int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n)
            return false;
        if (visited[x][y] || grid[x][y] == '0')
            return false;
        return true;
    }
}